#pragma once

//二叉链表示法
struct BiTNode
{
        int data;
        struct BiTNode* lchild;
        struct BiTNode* rchild;
};
typedef struct BiTNode   BiTNode;
typedef struct BiTNode* BiTree;
/*
//二叉链表示法简写
typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
*/

//三叉链表示法
typedef struct TriTNode
{
        int data;
        struct TriTNode *lchild, *rchild;
        struct TriTNode *parent;
}TriTNode, *TriTree;

//双亲链表示法
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{
        int data;
        int parentPosition; //指向双亲的指针 //数组下标
        char LRTag; //左右孩子标志域
}BPTNode;

typedef struct BPTree
{
        BPTNode nodes[MAX_TREE_SIZE]; //因为结点之间是分散的,需要把结点存储到数组中
        int num_node; //结点数目
        int root; //根结点的位置 //注意此域存储的是父结点在数组的下标
}BPTree;

//先序遍历：先遍历 根 再遍历 左 再遍历 右
//根 左 右
void DLR(BiTree tree);
//中序遍历：先遍历 左子树 再遍历 根 再遍历 右子树
// 左 根 右
void LDR(BiTree tree);
//后序遍历：先遍历左子树 再遍历 右子树 再遍历 根
//左 右 根
void LRD(BiTree tree);

//计算二叉树中叶子结点的数目
//采用先序遍历的递归算法
int countLeafNum(BiTree tree);

//计算二叉树的深度(高度)
int depth(BiTree tree);

//copy一个二叉树
BiTree copyTree(BiTree tree);

//中序遍历的非递归方法：先遍历 左子树 再遍历 根 再遍历 右子树 （左 根 右）
//中序遍历的非递归方法需要用到栈的模型 先走的后访问,后走的先访问显然是栈
void LDR_NonRecursive(BiTree tree);

//创建一个树
//#号补全法 前序遍历创建树
BiTree createBTree();

//后序遍历销毁一个树
void BiTree_Free(BiTNode* tree);
